// hdu5697
// 题意：
// 有n(<=400)道题，第i道题可以提高ai(<=800)智力点，代码量为bi(<=1000),
// 无聊值为ci(<=1000)，问至少提升m(<=sigma(ai))点智力点的情况下，
// 所做题的代码量之和*无聊值之和最小值为多少。
//
// 题解：
// 这是一道很类似最小乘积生成树的题，形式都是一样。理论还需要深入理解。
// 下面我们做一个初步分析。首先我们假设一个合理的解空间为XOY坐标系上的点。
// 那么要求的值就是该点横纵坐标乘积的最小值。
// 还是类似最小乘积生成树的那个性质，这个和的积的最小值可以等价为
// k*bi + t*ci 这样一个线性表示的和的最小值（反证法？）。
// 
// 对于这个和的乘积最小值对应解空间中点所构成的曲线是类似一个反比例函数的
// 曲线，我们就是要找到这条曲线上的点。那么我们可以先找到最左边的一个点A和
// 最下边B的一个点，他们的斜率做为那条直线的系数求出对应解空间中最小的点C，
// 然后递归的处理solve(A, C)和solve(C, B)，因为三角形ABC内的点肯定不会成为
// 那个曲线上的点。
//
// 然后这里计算一个解空间点的时候不同于最小乘积生成树跑的是最小生成树算法，
// 这里只需要一个dp，复杂度是O(n*sigma(a))。
// 然后递归的复杂度不太好算，但也不会太高，最坏情况是那种所有解空间的点
// 都在最优曲线上，这种情况有吗？
// 
// 有个图就更容易理解了。
//
// run: $exec < input
#include <iostream>
#include <algorithm>

struct point
{
	point() {}
	point(long long x, long long y) : x(x), y(y) {}
	long long x, y;
	long long value() const { return x * y; }
};

int const maxn = 500;
int const maxm = maxn * 1000;
long long inf = (1ll) << 60;
int a[maxn], b[maxn], c[maxn], p[maxn];
point tmp[maxm];
long long dp[maxm];
int n, m, sum;

point calc()
{
	tmp[0] = point(0, 0);
	dp[0] = 0;
	for (int i = 1; i <= sum; i++) dp[i] = inf;
	for (int i = 1; i <= n; i++)
		for (int j = sum; j >= a[i]; j--) {
			if (dp[j] > dp[j - a[i]] + p[i]) {
				dp[j] = dp[j - a[i]] + p[i];
				tmp[j] = point(tmp[j - a[i]].x + b[i], tmp[j - a[i]].y + c[i]);
			}
		}
	int pos = m;
	auto min = tmp[pos].value();
	for (int i = m + 1; i <= sum; i++)
		if (dp[i] < dp[pos] || (dp[i] == dp[pos] && tmp[i].value() < min))
			min = tmp[pos = i].value();
	return tmp[pos];
}

long long cross(point const& pa, point const& pb) { return pa.x * pb.y - pa.y * pb.x; }

long long solve(point const& pa, point const& pb)
{
	long long ret = std::min(pa.value(), pb.value());
	for (int i = 1; i <= n; i++)
		p[i] = (pb.x - pa.x) * c[i] + (pa.y - pb.y) * b[i];
	auto pc = calc();
	if (cross(point(pb.x - pa.x, pb.y - pa.y), point(pc.x - pa.x, pc.y - pa.y)) >= 0)
		return ret;
	ret = std::min(ret, solve(pa, pc));
	ret = std::min(ret, solve(pc, pb));
	return ret;
}

int main()
{
	std::ios::sync_with_stdio(false);
	while (std::cin >> n >> m) {
		sum = 0;
		for (int i = 1; i <= n; i++) {
			std::cin >> a[i] >> b[i] >> c[i];
			sum += a[i];
			p[i] = b[i];
		}
		auto pa = calc();
		for (int i = 1; i <= n; i++) p[i] = c[i];
		auto pb = calc();
		std::cout << solve(pa, pb) << '\n';
	}
}

